#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int>ans;
        for(int x:nums){
            bool fail=true;
            for(int y=0;y<=x*2;y++)
                if((y|(y+1))==x){
                    ans.push_back(y);
                    fail=false; break;
                }
            if(fail) ans.push_back(-1);
        } return ans;
    }
};

class Solution2 {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans;
        for(int x:nums){
            if(x==2) ans.push_back(-1);
            else{
                int p;
                for(p=0;x>>p&1;p++);
                ans.push_back(x^(1<<(p-1)));
            }
        }
        return ans;
    }
};

static const int N=3e3;
int f[N+10][N+10];
class Solution3 {
public:
    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        int n=source.size(),m=pattern.size(); bool flag[n+1];
        memset(flag,0,sizeof(flag));
        for(int x:targetIndices) flag[x+1]=true;
        const int INF=1e9;
        for(int i=0;i<=n;i++)for(int j=0;j<=m;j++) f[i][j]=-INF;
        f[0][0]=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(flag[i])f[i][j]++;
            if(j>0&&source[i-1]==pattern[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]);
        }
        return f[n][m];
    }
};

#define ll long long
class Solution4 {
public:
    int numberOfWays(int n,int x,int y) {
        const int MOD=1e9+7; ll f[n+1][x+1]; memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=x;j++)
                f[i][j]=(f[i-1][j]*j+f[i-1][j-1]*(x-j+1))%MOD;
        ll ans=0,p=1;
        for(int j=1;j<=x;j++){
            p=p*y%MOD;
            ans=(ans+f[n][j]*p)%MOD;
        } return ans;
    }
};

int main(){
    vector<int> nums={2,3,5,7};
    Solution s; vector<int> ans=s.minBitwiseArray(nums); for(auto x: ans) cout<<x<<" "; cout<<endl;
    Solution2 s2; vector<int> ans2=s2.minBitwiseArray(nums); for(auto x: ans2) cout<<x<<" "; cout<<endl;

    vector<int> targetIndices={0,1,2};
    Solution3 s3; cout<<s3.maxRemovals("abbaa","aba",targetIndices)<<endl;

    Solution4 s4; cout<<s4.numberOfWays(1,2,3)<<endl;
}